package com.lw.leetcode.dp.b;

/**
 * Created with IntelliJ IDEA.
 * dp
 * 1653. 使字符串平衡的最少删除次数
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/13 10:27
 */
public class MinimumDeletions {


    public static void main(String[] args) {
        MinimumDeletions test = new MinimumDeletions();

        // 2
        String str = "aababbab";

        // 2
//        String str = "bbaaaaabb";

        // 0
//        String str = "b";

        int i = test.minimumDeletions(str);
        System.out.println(i);
    }


    public int minimumDeletions(String s) {
        int le = s.length();
        int a1 = 0;
        int a2 = 0;
        for (int i = 0; i < le; i++) {
            if (s.charAt(i) == 'a') {
                a1++;
            }
        }
        int min = a1;
        for (int i = 0; i < le; i++) {
            if (s.charAt(i) == 'a') {
                a2++;
            }
            min = Math.min(min, i + 1 + a1 - (a2 << 1));
        }
        return min;
    }

}
